Models in computer graphics are often represented using triangle meshes. Geometrically, a triangle mesh (e.g., example portion of a triangle mesh 82 of FIG. 6) is a piecewise linear surface consisting of triangular faces joined together along their edges. In the following discussion, the geometry of a triangle mesh is denoted by a tuple (K,V), where K is a simplicial complex specifying the connectivity of the mesh simplices (i.e., the adjacency of the vertices, edges, and faces), and V={v.sub.1, . . . ,v.sub.m } is the set of vertex positions v.sub.j =(x.sub.j,y.sub.j,z.sub.j) defining the shape of the mesh in R.sup.3. More precisely, a parametric domain, .vertline.K.vertline..OR right.R.sup.m, is constructed by identifying each vertex of K with a canonical basis vector of R.sup.m, and the mesh is defined as the image, .phi..sub.v (.vertline.K.vertline.), where .phi..sub.v :R.sup.m .fwdarw.R.sup.3 is a linear map. (See, e.g., H. Hoppe et al., Mesh Optimization, 1993 Computer Graphics Proceedings 19-26.) The vertices of a triangle mesh (e.g., vertices 82-89 of the mesh 80 of FIG. 6) are denoted as v.sub.1, . . . ,v.sub.m ; the edges (e.g., 92-95) denoted by pairs of adjacent vertices as e={v.sub.j,v.sub.k }; and the faces (e.g., faces 100-107) denoted by triples of interconnected vertices as f={v.sub.j,v.sub.k,v.sub.l }.
In typical computer graphics applications, surface appearance attributes other than geometry (i.e., the above described simplicial complex and vertex positions tuple (K,V)) are also associated with the mesh. These attributes can be categorized into two types: discrete attributes and scalar attributes. Discrete attributes are usually associated with faces of the mesh. A common discrete attribute, the material identifier, determines the shader function used in rendering a face of the mesh, as well as some of the shader function's global parameters. As an example, a trivial shader function may involve simple look up within a specified texture map. (See, e.g., S. Upstill, The RenderMan Companion (Addison-Wesley 1990).)
Many scalar attributes are often associated with a mesh, including diffuse color (r,g,b), normal (n.sub.x,n.sub.y,n.sub.z), and texture coordinates (u,v). More generally, these attributes specify the local parameters of shader functions defined on the mesh faces. To capture discontinuities in the scalar fields, and because adjacent faces may have different shading functions, it is common to associate scalar attributes not with vertices of a mesh, but with its corners. (See, e.g., Apple Computer, Inc., 3d Graphics Programming with QuickDraw 3d (Addison-Wesley 1995).) A corner is defined as a (vertex,face) tuple. Scalar attributes s.sub.(v,f) at a corner c=(v.sub.j,f.sub.k) specify the shading parameters for face f at vertex v. As an example, to model a crease (a curve on the surface across which the normal field is not smooth), one identifies a curve (sequence of edges) in the mesh; at each vertex along its path, the curve partitions the corners into two sets; two normals are associated with the vertex, one for each of these sets. A mesh with scalar and discrete surface attributes is thus denoted as a tuple M=(K,V,D,S) where D is the set of discrete attributes d.sub.f associated with the faces f={v.sub.j,v.sub.k,v.sub.l }.di-elect cons.K, and S is the set of scalar attributes S.sub.(v,f) associated with the corners (v,f) of K.
In the continuing quest for realism in computer graphics, highly-detailed geometric models are rapidly becoming commonplace. Using current modeling systems, authors can create highly detailed geometric models of objects by applying versatile modeling operations (e.g., extrusion, constructive solid geometry ("CSG"), and free-form deformations ("FFD")) to a vast array of geometric primitives (e.g., non-uniform rational B-spline ("NURBS") and implicit surfaces ("Blobbies")). (See, T. Sederberg and S. Parry, Free-form Deformation of Solid Geometric Models, 1986 Computer Graphics Proceedings FFD!; Rockwood, Real-time Rendering of Trimmed Surfaces, 1989 Computer Graphics Proceedings NURBS!; and J. Blinn, A Generalization of Algebraic Surface Drawing, 1982 ACM Transactions on Graphics 1(3)235-256 Blobbies!.) For display purposes, these authored models are usually tessellated into triangle meshes of the type previously described. Detailed models can also be rapidly obtained by scanning physical objects with structured light systems, for instance laser range scanners, to also create meshes. In either case, the resulting complex meshes are expensive to store, transmit, and render, thus motivating a number of practical problems.
Mesh Simplification. The meshes created by modeling and scanning systems are typically not optimized for display performance. In most applications, these initial meshes can usually be replaced by nearly indistinguishable approximations with far fewer faces, thereby improving rendering efficiency. At present, the computer user (e.g., graphical artist or designer) is often responsible for this hand-tuning of meshes, much the same way programmers tinkered with assembly code before the advent of optimizing compilers. A far better approach is to develop mesh simplification tools to automate this painstaking task. As another benefit, such tools allow porting of a single model to platforms of varying performance.
Level-of-Detail Approximation. When a detailed mesh is far from the viewer, it may occupy only a small region of the screen. Significant work must be expended to render the mesh only to have it affect a small number of pixels. Instead, a far coarser mesh (i.e., one with fewer vertices and faces) would look almost identical. To address this problem, many applications use several versions of a model at various levels of detail. A fully detailed mesh is used when the object is close; coarser approximations are substituted as the object recedes. (See, T. A. Funkhouser and C. H. Sequin, Adaptive Display Algorithm for Interactive Frame Rates During Visualization of Complex Virtual Environments, 1993 Computer Graphics Proceedings 247-254). Further, instantaneous switching between two levels-of-detail of a given model can lead to a perceptible "popping" display effect. For this reason, the capability of constructing smooth visual transitions--called geomorphs--between meshes having different levels-of-detail is desirable.
Progressive transmission. A complex mesh consumes considerable time to transmit over a communication line, often many times longer than it takes to visually render images with views on the mesh. When a mesh is transmitted over a communication line, one would like to render views that show progressively better approximations to the model as data is incrementally received. The simplest known approach is to render the individual triangles as they are received, but of course this looks extremely poor. Another prior approach is to transmit successive level-of-detail approximations, but this requires additional transmission time.
Mesh compression. A model should be stored in the smallest amount of memory or disk space. There have been two orthogonal approaches to dealing with this problem. One is to use mesh simplification, as described earlier, to reduce the number of faces in the model as much as possible while preserving its appearance. The other is mesh compression: minimizing the space taken to store the model given that a particular mesh has been selected.
Selective refinement. When switching to a more detailed mesh of a level-of-detail representation, detail is added uniformly over the model's surface. For some models, it is desirable to refine the mesh only in selected regions. For instance, as a user flies over a terrain model, one would like to show the terrain in full detail only near the viewer, and only within the field of view.
There exist a number of mesh simplification techniques that address these problems with varying success. A technique described in G. Turk, Re-Tiling Polygonal Surfaces, 1992 Computer Graphics Proceedings 55-64 hereafter "Turk92"!, sprinkles a set of points on a mesh, with density weighted by estimates of local curvature, and then retriangulates based on those points.
Both W. J. Schroeder et al., Decimation of Triangle Meshes, 1992 Computer Graphics Proceedings 65-97 hereafter "Schroeder-etal92"! and A. Varshney, Hierarchical Geometric Approximations, PhD thesis, Department of Computer Science, University of North Carolina at Chapel Hill (1994) hereafter "Varshney94"! describe techniques that iteratively remove vertices from the mesh and retriangulate the resulting holes. The technique in Varshney94 is able to bound the maximum error of the approximation to a user-specified tolerance by defining two offset surfaces to the original mesh and using combinatorial searching.
H. Hoppe et al., Mesh Optimization, 1993 Computer Graphics Proceedings 19-26 hereafter Hoppe93! describes a technique, referred to as mesh optimization, which simplifies an arbitrary original mesh by applying successive transformations selected from a set including edge collapse, edge split and edge swap so as to minimize an energy function. As shown by a graph 25 of FIG. 2 having an accuracy axis 26 and a conciseness axis 27, this energy function explicitly models the competing goals of accuracy and conciseness by sampling a dense set of points from the original mesh, and using these points to define a distance metric between a more simplified mesh resulting from a selected transformation and the original mesh.
More specifically, the goal of the mesh optimization method described in Hoppe93 is to find a mesh M=(K,V) that both accurately fits a set X of points x.sub.i .di-elect cons.R.sup.3 and has a small number of vertices. This problem is cast as minimization of an energy function EQU E(M)=E.sub.dist (M)+E.sub.rep (M)+E.sub.spring (M) (1)
of accuracy and conciseness: the distance energy term EQU E.sub.dist (M)=.SIGMA..sub.i d.sup.2 (x.sub.i,.phi..sub.v (.vertline.K.vertline.)) (2)
measures the total squared distance of the points from the mesh (i.e., a measurement along the accuracy axis 26), and the representation energy ter m EQU E.sub.crep (M)=c.sub.rep m (3)
penalizes the number m of vertices in M (i.e., a measurement along the conciseness axis 27).
The third term, the spring energy E.sub.spring (M) is introduced to regularize the optimization problem. It corresponds to placing on each edge of the mesh a spring of rest length zero and tension .kappa.: EQU E.sub.spring (M)=.SIGMA..sub.{j,k}.epsilon.K .kappa..parallel.v.sub.j -v.sub.k .parallel..sup.2 ( 4)
Hoppe93 describes minimizing the energy function E(M) using a nested optimization method having an outer loop and an inner loop. In the outer loop, the method optimizes over K, the connectivity of the mesh, by randomly attempting a set of three possible mesh transformations: edge collapse, edge split, and edge swap. This set of transformations is complete, in the sense that any simplicial complex K of the same topological type as K can be reached through a sequence of these transformations. For each candidate mesh transformation, K.fwdarw.K', the continuous optimization described below computes E.sub.K', the minimum of E subject to the new connectivity K'. If .DELTA.E=E.sub.K' -E.sub.K is found to be negative, the mesh transformation is applied (akin to a zero-temperature simulated annealing method).
In the inner loop performed for each candidate mesh transformation, the method computes E.sub.K' =min.sub.v E.sub.dist (V)+E.sub.spring (V) by optimizing over the vertex positions V. For the sake of efficiency, the algorithm in fact optimizes only one vertex position v.sub.s, and considers only the subset of points X that project onto the neighborhood affected by K.fwdarw.K'.
The regularizing spring energy term E.sub.spring (M) is found in Hoppe93 to be most important in the early stages of the optimization. The optimization method therefore achieves best results by repeatedly invoking the nested optimization method described above with a schedule of decreasing spring constants .kappa..
Hoppe93 also demonstrates use of this mesh optimization method as a mesh simplification tool. Given an initial mesh M (e.g., example initial arbitrary mesh shown in FIG. 1(a)) to approximate, a dense set of points X is sampled both at the vertices of M and randomly over its faces. The optimization method is then invoked with initial mesh M as the starting mesh. By varying the setting of the representation constant c.sub.rep, the optimization method takes different paths 34-36 through a space of possible meshes 38 and thereby can produce optimized meshes M.sub.b, M.sub.c, and M.sub.d with different trade-offs of accuracy and conciseness For example, FIGS. 1(b-d) show views of three example optimized meshes M.sub.b, M.sub.c, and M.sub.d, respectively, produced from the example original arbitrary mesh (FIG. 1(a)) by the prior mesh optimization method of Hoppe93 for different values of the representation constant c.sub.rep.
J. Rossignac and P. Borrel, Multi-resolution 3D Approximations for Rendering Complex Scenes, Modeling in Computer Graphics 455-465 (Springverlag, N.Y. 1993) hereafter "Rossignac-Borrel93"! describes a technique of merging vertices of a model using spatial binning. A unique aspect of their approach is that the topological type of the model may change in the process. Their scheme is extremely fast, but since they ignore geometric qualities like curvature, their approximations are far from optimal.
The above-described mesh simplification techniques create a discrete hierarchy of simplified models by successively applying their simplification method several times. Both Turk92 and Rossignac-Borrel93 are able construct geomorphs between the discrete set of models thus created.
More recently, M. Lounsbery et al., Multiresolution analysis for surfaces of arbitrary topological type, Technical Report 93-10-05b, (Department of Computer Science and Engineering, University of Washington, January 1994) hereafter Lounsbery-etal94! have generalized the concept of multiresolution analysis to surfaces of arbitrary topological type. M. Eck et al., Multiresolution Analysis of Arbitrary Meshes, 1995 Computer Graphics Proceedings 173-182 hereafter "Eck95"! describes how this wavelet-based multiresolution approach can be applied to the approximation of an arbitrary mesh. They first construct a parameterization of the mesh over a simple domain, and then expand that parameterization on a wavelet basis. They are able to bound the maximum error between the original mesh and any approximation.
In the present invention, the above problems are addressed by methods and apparatus for storing, transmitting and rendering views of an arbitrary polygonal mesh M using a format, referred to herein as a progressive mesh ("PM") representation, that represents the arbitrary polygonal mesh as a much coarser mesh M.sup.0 together with a sequence of n detail records that indicate how to incrementally refine M.sup.0 exactly back into the original mesh M=M.sup.n. In an illustrated embodiment of the invention, each of these records stores information associated with a vertex split, an elementary mesh transformation that adds an additional vertex to the mesh. The PM representation of M thus defines a continuous sequence of meshes M.sup.0,M.sup.1, . . . ,M.sup.n of increasing accuracy from which level-of-detail approximations with any desired complexity can be efficiently retrieved. Moreover, smooth visual transitions (geomorphs) can be efficiently constructed between any two such meshes. In addition, the PM representation naturally supports progressive transmission, offers a concise encoding of M itself, and supports efficient selective refinement. In short, the PM representation offers an efficient, lossless, continuous-resolution representation.
The present invention also provides a new simplification procedure for constructing a PM representation from a given mesh M. Unlike previous simplification methods, this procedure seeks to preserve not just the geometry of the mesh surface, but also its overall appearance, as defined by the discrete and scalar attributes associated with its surface.
Of the prior mesh simplification techniques discussed above, the multiresolution analysis (MRA) approach of Eck95 has some similarities with the PM representation. The MRA approach also stores a simple base mesh, together with a stream of information that progressively adds detail back to the model. The MRA approach likewise produces a continuous-resolution representation from which approximations of any complexity can be extracted. However, the PM representation of the present invention has a number of differences from and advantages over the prior MRA approach.
First, the MRA approach utilizes detail terms in the form of wavelets that specify transformations which recursively split the faces of a base mesh. This requires the detail terms or wavelets to lie on a domain with subdivision connectivity. As a result, each level of detail approximation, including the highest, must belong to a restricted class of meshes (those with subdivision connectivity). An arbitrary initial mesh M (with arbitrary connectivity) can only be approximately recovered to within an .di-elect cons. tolerance, and never exactly.
In contrast, the PM representation of the present invention is lossless. Each detail record is a complete mesh refinement transformation which can produce progressive meshes (M.sup.i, i&lt;n of the PM representation) having any arbitrary connectivity. As a result, the progressive meshes can be much better approximations geometrically of the original arbitrary mesh M than the counterpart approximating meshes of the MRA approach. Furthermore, the highest-detailed model in the continuous-resolution family, M.sup.n, is exactly the original arbitrary mesh M. (Compare, e.g., the illustrative MRA approach meshes shown in FIGS. 4(a-d) to the illustrative PM representation meshes shown in FIGS. 7(a-d).)
Additionally, the MRA approach cannot deal effectively with surface creases (curves on the surface across which the surface is not smooth), unless those creases happen to lie parametrically along edges of the base (least level of detail) mesh. The progressive meshes constructed according to the invention, however, can introduce surface creases anywhere on the mesh surface and at any of the levels-of-detail.
Additionally, the PM representation can capture both continuous, piecewise-continuous, and discrete appearance attributes associated with the surface. Such attributes include diffuse color, normals, texture coordinates, material identifiers, and shader parameters. To represent functions with discontinuities, prior MRA schemes can use piecewise-constant basis functions, but then the resulting approximations have too many discontinuities since none of the basis functions meet continuously. (See, e.g., P. Schroder and W. Sweldens, Spherical Wavelets: Efficiently Representing Functions on the Sphere, 1995 Computer Graphics Proceedings 161-172 (the Haar wavelet basis).) Furthermore, it is not presently clear how MRA could be extended to capture discrete attributes.
Finally, the PM representation of the invention allows geomorphs between any two levels-of-detail meshes with different discrete attributes. This is not possible with prior MRA approaches.
Additional features and advantages of the invention will be made apparent from the following detailed description of an illustrated embodiment which proceeds with reference to the accompanying drawings.